package Tree.BSTTree;


import javax.management.ObjectName;
import java.util.LinkedList;

/**
 * @className:
 * @description:
 * @author: myself
 * @date:
 * @version: 0.1
 * @since: JDK17
 */

public class BSTTree1 {
    //对BSTTree进行属性的操作
    BSTNode root;


    //这里设置对应的节点类
    static class BSTNode{
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private Object daGet(BSTNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            //查找的值小，向左找
            return daGet(node.left,key);
        }
        if (key > node.key) {
            //查找的值大，向左找
            return daGet(node.right,key);
        }
        return node.value;
    }

    /**
     * 根据key查找对应的元素
     * @param key：要查找的元素的key
     * @return：返回的元素
     */
    public Object get(int key) {
        //使用递归，借助doGet方法
        /*
        * return daGet(root,key);
        * */
        /*不使用递归*/
        BSTNode node=root;
        while (node != null) {
            if (key < node.key) {
                //查找的值小，向左找
                node = node.left;
            }else
            if (key > node.key) {
                //查找的值大，向左找
                node = node.right;
            }else {
                return node.value;
            }
        }
        return null;
    }

    /**
     * 查找树中最小关键字对应的值
     *
     * @return：关键字对应的值
     */
    private Object doMin(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }
    public Object min() {
        /*递归实现
        * return doMin(root)*/

        /*非递归实现*/
        if (root == null) {
            return null;
        }
        BSTNode node = root;
        while (node.left!= null) {
            node = node.left;
        }
        return node.value;
    }

    /**
     * 查找树中最大关键字对应的值
     * @return：关键字对应的值
     */
    private Object doMax(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMin(node.right);
    }
    public Object max() {
        /*递归实现
         * return doMax(root)*/

        /*非递归实现*/
        if (root == null) {
            return null;
        }
        BSTNode node = root;
        while (node.right!= null) {
            node = node.right;
        }
        return node.value;
    }

    /**
     * 存储关键字和对应的值
     *
     * @param key：关键字
     * @param value：关键字对应的值
     *//*
    private Object daPut(BSTNode node, int key, Object value) {
    }*/
    public void put(int key, Object value) {
        BSTNode node=root;
        BSTNode parent = null;//找新加入的节点的父节点
        while (node != null) {
            parent = node;//需要找个这个父节点，用来处理新加入的
            if (key < node.key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                //代表已经有该Key对应的节点，我们要做的就是对该节点进行一个更新
                node.value = value;
                return;
            }
            //代表这里没有那个值，我们需要新建相关的节点来完善该二叉搜索树
            }
        if (parent == null) {//确定初始树不为空
            root = new BSTNode(key, value);
        }else if (key < parent.key) {//进行节点的左节点还是右节点的判断
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * 查找关键字的后继值
     * @param key：关键字
     * @return：后继值
     */
    public Object successor(int key) {
        //1.先在二叉搜索树中找到该key对应的节点
        BSTNode p = root;
        BSTNode ancestorFromRight=null;//（2)使用
        while (p!= null) {
            if (key < p.key) {
                p = p.left;
                ancestorFromRight = p;
            } else if (key > p.key) {
                p = p.right;
            }else {
                break;
            }
        }
        //2.先判断是否有该key对应的节点
        if (p == null) {
            return null;
        }
        //3. 找到节点后
        //(1)：若是该节点有右子树，那么右子树的最小值就是该数的前驱（例如该图中的7节点）
        //(2)：若是该节点没有右子树，若是离他最近的，自右而来的节点就是他的前任（例如该图中的3节点）

        //（1）
        if (p.right != null) {
            //对min()方法进行简单修改
            BSTNode node = p.right;
            while (node.left!= null) {
                node = node.left;
            }//此时node就是右子树最小节点
            return node.value;
        }

        //（2）这里直接返回就行
        return ancestorFromRight!=null?ancestorFromRight.value:null;
    }

    /**
     * 查找关键字的前驱值
     * @param key：关键字
     * @return：前驱值(找比key小1的值)
     */
    public Object predecessor(int key) {
        //1.先在二叉搜索树中找到该key对应的节点
        BSTNode p = root;
        BSTNode ancestorFromLeft=null;//（2)使用
        while (p!= null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                ancestorFromLeft = p;
                p = p.right;
            }else {
                break;
            }
        }
        //2.先判断是否有该key对应的节点
        if (p == null) {
            return null;
        }
        //3. 找到节点后
        //(1)：若是该节点有左子树，那么左子树的最大值就是该数的前驱（例如该图中的2节点）
        //(2)：若是该节点没有左子树，若是离他最近的，自左而来的节点就是他的前任（例如该图中的5节点）

        //（1）
        if (p.left!= null) {
            //对max()方法进行简单修改
            BSTNode node = p.left;
            while (node.right!= null) {
                node = node.right;
            }//此时node就是右子树最小节点
            return node.value;
        }

        //（2）这里直接返回就行
        return ancestorFromLeft!=null?ancestorFromLeft.value:null;
    }

    /**
     * <h3>根据关键字删除</h3>
     *
     * @param key 关键字
     * @return 被删除关键字对应值
     */
    public Object delete(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (key < p.key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        // 删除操作
        if (p.left == null) {
            shift(parent, p, p.right); // 情况1
        } else if (p.right == null) {
            shift(parent, p, p.left); // 情况2
        } else {
            // 情况4
            // 4.1 被删除节点找后继
            BSTNode s = p.right;
            BSTNode sParent = p; // 后继父亲
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            // 4.2 删除和后继不相邻, 处理后继的后事
            if (sParent != p) {
                shift(sParent, s, s.right); // 不可能有左孩子
                s.right = p.right;
            }
            // 4.3 后继取代被删除节点
            shift(parent, p, s);
            s.left = p.left;
        }
        return p.value;
    }

    /**
     * 托孤方法
     *
     * @param parent  被删除节点的父亲
     * @param deleted 被删除节点
     * @param child   被顶上去的节点
     */
// 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    public static void main(String[] args) {
        BSTTree1 bstTree1 = new BSTTree1();
        bstTree1.put(1, 23);
        bstTree1.put(2, 33);
        bstTree1.put(4, 43);
        System.out.println(bstTree1.get(4));
        System.out.println(bstTree1.predecessor(2));
        System.out.println(bstTree1.successor(2));
    }
}
